package cn.lishiyuan.leetcode;

import cn.lishiyuan.algorithm.heap.Heap;

/**
 * 面试题 17.14. 最小K个数
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
 * 示例：
 *
 * 输入： arr = [1,3,5,7,2,4,6,8], k = 4
 * 输出： [1,2,3,4]
 * 提示：
 *
 * 0 <= len(arr) <= 100000
 * 0 <= k <= min(100000, len(arr))
 */
public class SmallestK {

    public static Integer[] resolve(Integer[] nums ,int k){
        Integer[] res = new Integer[k];

        Heap<Integer> heap = new Heap<>(Heap.HeapType.BIG,k);

        for (int i = 0; i < nums.length; i++) {
            if(i < k){
                // 先放入k个
                heap.add(nums[i]);
            }else {
                Integer big = heap.top();
                if(big > nums[i]){
                    // 最大元素大于则替换元素
                    heap.removeTop();
                    heap.add(nums[i]);
                }
            }
        }
        for (int i = 0; i < k; i++) {
            res[k-i-1] = heap.removeTop();
        }
        return res;
    }



}
